import java.util.Arrays;

public class Test1 {
    //leetcode 978 最长湍流子数组
    /**
     * 方法一：使用一个dp表
     * 通过arr[i] arr[i-1] arr[i-2]三个数的状态来判断湍流子数组的长度
     * @param arr
     * @return
     */
    public int maxTurbulenceSize1(int[] arr) {
        //dp[i]表示以i位置为结尾的所有子数组中最长的湍流子数组
        int n = arr.length;
        if (n == 1) return 1;
        int[] dp = new int[n];
        dp[0] = 1;
        dp[1] = arr[0] == arr[1] ? 1 : 2;
        int ret = dp[1];
        for (int i = 2; i < n; i++) {
            if (arr[i] == arr[i-1]) dp[i] = 1;
            else if (arr[i] > arr[i-1]) dp[i] = arr[i-1] < arr[i-2] ? dp[i-1] + 1 : 2;
            else dp[i] = arr[i-2] < arr[i-1] ? dp[i-1] + 1 : 2;
            ret = Math.max(dp[i],ret);
        }
        return ret;
    }

    public int maxTurbulenceSize2(int[] arr) {
        //定义两个dp表，f[i]表示以i位置为结尾的状态为上升状态的最长湍流子数组，
        //g[i]表示以i位置为结尾的状态为下降状态的最长湍流子数组
        int n = arr.length;
        int[] f = new int[n],g = new int[n];
        Arrays.fill(f,1);Arrays.fill(g,1);
        int ret = 1;
        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[i-1]) f[i] = g[i-1] + 1;
            else if (arr[i] < arr[i-1]) g[i] = f[i-1] + 1;
            ret = Math.max(ret,Math.max(f[i],g[i]));
        }
        return ret;
    }
}
